//
// Created by Administrator on 2021/4/9.
//
//给定一个二叉树，判断它是否是高度平衡的二叉树。
//
//本题中，一棵高度平衡二叉树定义为：
//
//一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
#include <iostream>

using namespace std;

//definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {  // 自顶向下递归
public:
    // 返回一个节点的高度
    int depth(TreeNode *root) {
        if (!root) return 0;
        return max(depth(root->left), depth((root->right))) + 1;
    }

    bool isBalanced(TreeNode *root) {  // 递归
        if (!root) return true; // 空节点的左右子树是平衡的
        return (abs(depth(root->left) - depth(root->right)) <= 1) and
               (isBalanced(root->left) and isBalanced(root->right));
    }
    // 好像重复计算比较多
};

class Solution2 {  // 自底向上递归
public:
    int height(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
            return -1;   // 该节点的左右子节点不平衡，返回-1
        } else {
            return max(leftHeight, rightHeight) + 1;  // 返回该节点高度
        }
    }

    bool isBalanced(TreeNode *root) {
        return height(root) >= 0;
    }
};

int main() {
    auto t5 = TreeNode(7);
    auto t4 = TreeNode(15);
    auto t3 = TreeNode(20, &t4, &t5);
    auto t2 = TreeNode(9);
    auto t1 = TreeNode(3, &t2, &t3);

    auto n7 = TreeNode(4);
    auto n6 = TreeNode(4);
    auto n5 = TreeNode(3);
    auto n4 = TreeNode(3, &n6, &n7);
    auto n3 = TreeNode(2);
    auto n2 = TreeNode(2, &n4, &n5);
    auto n1 = TreeNode(1, &n2, &n3);

    Solution2 sol;
    std::cout << (sol.isBalanced(&t1) ? "true" : "false") << std::endl;
    std::cout << (sol.isBalanced(&n1) ? "true" : "false") << std::endl;


    return 0;
}